class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int rex[4]={0,0,1,-1};
    int rey[4]={1,-1,0,0};
    vector<vector<int>> menu;
    int solve(vector<vector<int> >& matrix) {
        int mx=matrix.size();
        int my=matrix[0].size();
        menu.resize(mx,vector<int>(my,0));
        int maxLen=0;
        for(int i=0;i<mx;i++)
        {
            for(int j=0;j<my;j++)
            {
                maxLen=max(maxLen,dfs(i,j,matrix,mx,my));
            }
        }
        return maxLen;
    }
    int dfs(int x,int y,vector<vector<int> >& matrix,int mx,int my)
    {
        if(menu[x][y]){
            return menu[x][y];
        }
        int maxPath=1;
        for(int i=0;i<4;i++)
        {
            int x1=x+rex[i];
            int y1=y+rey[i];
            if(x1>=0&&x1<mx&&y1>=0&&y1<my&&matrix[x1][y1]>matrix[x][y])
            {
                maxPath=max(maxPath,dfs(x1,y1,matrix,mx,my)+1);
            }
        }
        menu[x][y]=maxPath;
        return maxPath;
    }
};
